#include <bits/stdc++.h>
using namespace std;

/*
2131. 连接两字母单词得到的最长回文串
已解答
中等
相关标签
相关企业
提示
给你一个字符串数组 words 。words 中每个元素都是一个包含 两个 小写英文字母的单词。

请你从 words 中选择一些元素并按 任意顺序 连接它们，并得到一个 尽可能长的回文串 。每个元素 至多 只能使用一次。

请你返回你能得到的最长回文串的 长度 。如果没办法得到任何一个回文串，请你返回 0 。

回文串 指的是从前往后和从后往前读一样的字符串。

 

示例 1：

输入：words = ["lc","cl","gg"]
输出：6
解释：一个最长的回文串为 "lc" + "gg" + "cl" = "lcggcl" ，长度为 6 。
"clgglc" 是另一个可以得到的最长回文串。
示例 2：

输入：words = ["ab","ty","yt","lc","cl","ab"]
输出：8
解释：最长回文串是 "ty" + "lc" + "cl" + "yt" = "tylcclyt" ，长度为 8 。
"lcyttycl" 是另一个可以得到的最长回文串。
示例 3：

输入：words = ["cc","ll","xx"]
输出：2
解释：最长回文串是 "cc" ，长度为 2 。
"ll" 是另一个可以得到的最长回文串。"xx" 也是。
 

提示：

1 <= words.length <= 105
words[i].length == 2
words[i] 仅包含小写英文字母。
*/

// 法一
class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        unordered_map<string, int> freq;
        for (const string& word : words) {
            freq[word]++;
        }

        int len = 0;
        bool central = false;

        // 键值对 与 键值对 类型对应 哈希表来存储
        for (const auto& [word, count] : freq) {
            if (word[0] == word[1]) {
                // 自身回文
                if (count % 2 == 1)     central = true;
                len += 2 * (count / 2 * 2);
            } else {
                string reversed = {word[1], word[0]};
                if (freq.count(reversed)) {
                    int min_pairs = min(count, freq[reversed]);
                    len += 4 * min_pairs;
                    freq[word] = 0;
                }
            }
        }
        if (central)    len += 2;
        return len;
    }
};

// 法二
class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        // 初始化一个26x26的数组来统计每个单词的出现次数
        int cnt[26][26] = {};
        int ans = 0;
        // 遍历所有单词，统计每个单词的出现次数
        for (auto& w : words) {
            ++cnt[w[0] - 'a'][w[1] - 'a'];
        }
        bool center = false;
        // 遍历所有可能的字符组合
        for (int i = 0; i < 26; ++i) {
            // 处理自身回文的单词（如 "aa"）
            int c = cnt[i][i];
            // 如果出现次数为奇数，可以有一个单词放在中心
            if (c & 1) {
                center = true;
            }
            // 计算可以配对的自身回文单词对数，每对增加2的长度
            ans += c & ~1;
            // 处理非自身回文的单词（如 "ab" 和 "ba"）
            for (int j = i + 1; j < 26; ++j) {
                // 取 "ab" 和 "ba" 的最小出现次数，每对增加4的长度
                ans += min(cnt[i][j], cnt[j][i]) * 2;
            }
        }
        // 如果存在中心单词，总长度增加2
        return (ans + center) * 2;
    }
};